A “project,” as that term is used herein, includes many individual activities, each of which requires certain amount of time and resources to be completed. Project scheduling is the problem of finding the starting times and the execution modes of the activities such that the prescribed constraints on resources and the prescribed relations between activities are satisfied and an objective function is optimized.
In a project scheduling problem, a set of activities and a project deadline in form of time are given. All activities should be finished before the deadline. A set of resources that are required by the execution of activities is given. The execution of each activity requires time and resources, and the starting and finishing times are subject to constraints such as precedence relations and temporal relations to the times of the other activities.
With each activity, one or a set of execution modes is given. Each execution mode specifies a profile of the execution of the activity that contains durations, certain resources and their amount, and the resulting profit. Resources can be of different types. Renewable resources are assumed to have constant availability during the whole project period. Each activity may occupy a certain amount of renewable resources during its execution. The total amount of each renewable resource, however, is typically limited. Therefore, certain sets of activities that together require more than available renewable resources cannot be executed simultaneously.
Some examples of renewable resources are human specialists and tools. Nonrenewable resource, like materials and combustibles, are depleted after being used for performing activities. The total availability of each nonrenewable resource is given as constraints. Other types of resources may also be present.
In addition to being subject to resource availability, the execution of activities is also subject to the prescribed precedence or temporal constraints mentioned above. The precedence constraints are in the form of pair-wise orders between the starts and finishes of activities (e.g., Activity B must start after Activity A is finished). The temporal constraints generalize the precedence constraints by introducing specific time or length of time to the precedence relations. A temporal constraint between events A and B should specify the minimum or the maximum delay between events A and B.
A feasible solution of the project scheduling problem includes the starting times of all activities and their execution modes such that all constraints and the deadline are met. There may or may not exist any feasible solution, and there may exist more than one feasible solution. A given objective function measures the quality of a solution. An objective function may be a combination of multiple sub-objectives which often conflict with one another (e.g., minimizing the resource usage while also minimizing the project duration). The project scheduling problem is to find a feasible solution such that the given objective function is optimized (mathematically, either minimized or maximized).
Several factors have been found by the inventors to be important to project execution of the type discussed herein and may significantly affect the total project cost. Each of the following factors is discussed in more detail below:
1. While the starts and finishes of individual activities may have a certain level of flexibility, the entire project must be finished before a given deadline. Violating that deadline may incur high penalty.
2. Resource (personnel, tools, materials, and etc.) costs are the dominant portion of project expenses.
3. The amount of certain resources is not linearly related to the amount of work. Those resources may be shared by the multiple activities that are executed simultaneously.
4. Activities may be executed in multiple modes. Those are often the tradeoffs among duration and different resources.
5. Sequence-dependent activity setup time and costs can be significant.
6. The relations between activities are sometimes better characterized by temporal constraints than precedence constraints.
7. Different objectives, which may conflict with each other, are present. All of the objectives should be considered in a balanced way.
Factors 1 and 2 are dealt with in most existing techniques for optimizing project schedules. There is, however, presently a need for an integrated model that considers all the factors so that the solution is optimized more accurately. While formulation of such an integrated model has been attempted in the past, such attempts have failed because of the lack of mathematical modeling techniques and the limited computational powers to solve problems in a real-world size. Those difficulties are integrated, because better modeling gives more efficient algorithms and, thus, problems of larger size can be numerically solved.
The third factor listed above relates to resource sharing. Resource sharing is rarely considered in the literature and in most existing software; however, it happens very often in the real world. For example, carpooling and room sharing are instances of resource sharing. Resource sharing exhibits a nonlinear relation between the required amount of resources and the amount of work they serve because the same resource might be used and shared by multiple activities that are executed simultaneously and near the same location. While individual activities should be scheduled at their best times, a trade-off of individual best timing to increased sharing of resources may lower the overall cost. There is a need for a model wherein that trade-off is considered and balanced with other objectives.
The fourth factor above considers multiple execution modes. Activities can be performed in different modes. Each mode of an activity is associated with a profile, which specifies the activity duration, the consumption of resources, quality, and profits. Typical multiple modes are the trade-offs between time and resources, time and quality, and even between different resources.
The fifth factor above relates to sequence-dependent setup time/costs. That concept was originally associated with single-machine production scheduling. The inventors have generalized it and associated it with the concept of personnel traveling and resource transportation. Traveling and resource transportation often incur large expenses in on-site service projects. When a group of specialists, together with the tools, materials, and combustibles, are involved in serving at sites all over a nation or even the world, the traveling and transportation time and costs can be significant. The coding of start/finish event orders (described below) fundamentally enables the sequence-dependent setup time and costs to be easily evaluated and optimized as one of the objectives.
The sixth factor takes into account temporal constraints. The relationships between the activities in certain time sensitive real-world applications must be presented by the temporal constraints, instead of the simpler precedence constraints. The temporal constraints generalize the traditional precedence constraints. Older project scheduling models only allow users to specify precedence constraints and will return schedules in which the starts of the activities satisfy the prescribed precedence. On one hand, in time-critical industries such as chemical engineering and food processing, certain activities must be done within given time frames, not too early after their preceding activities are finished and not too late after either. Temporal constraints model that by specifying the minimum and maximum delays between activities. On the other hand, in most industries, storing products between processes also incurs costs, which are omitted in older scheduling techniques. The storage of products for further processes may be modeled as activities that start immediately after the preceding process finishes and end immediately before the succeeding process begins and has varying durations (i.e., multi modes).
The seventh factor relates to the plural objectives of the project. Most project scheduling models in the literature and most commercial scheduling software only minimize project makespans. In other words, they optimize worst-case task durations. While minimizing makespan is an important purpose of traditional production scheduling, it is not the only one. For example, in service event scheduling, the service events are usually roughly scheduled so the main means of optimally scheduling the activities of services and determining their execution modes is to evenly schedule the utilization of rare and expensive resources. A lot of real world objectives are “non-regular;” i.e., generally speaking, the objective may not be improved by scheduling activities earlier. Consequently, scheduling problems with non-regular objectives are considered harder than those with regular objectives. Some examples of regular objectives are: the minimization of makespan, weighted delays, the total number of tardy activities, and/or the total (weighted) resource consumption as well as any combination of “regular” objectives. In contrast, “non-regular” objectives include the minimization of renewable resource leveling, setup time/cost, earliness, the total number of early activities and/or the maximization of net present value as well as the optimization of any combination of “regular” and “non-regular” objectives.
There is therefore presently a need to provide a model that consolidates at least some of those concepts into an integrated problem and a technique that solves the problem. Particularly, there is a need for a technique for efficiently solving a scheduling network in a project having a small to medium number of tasks and expensive resources that must be shared among tasks. To the inventors' knowledge, no such techniques are currently available.